1. Field of the Invention
The present invention concerns telecommunication networks and more particularly the routing of calls in a telecommunication network, in particular in a private network, in which calls have different priorities.
2. Description of the Prior Art
Private telecommunication networks are made up of communication nodes interconnected by trunks conveying calls and/or signaling. A description of physical and virtual private networks can be found in xe2x80x9cLe RNIS appliquxc3xaau Centrex et aux rxc3xaseaux privxc3xas virtuelsxe2x80x9d [xe2x80x9cThe ISDN applied to Centrex and to virtual private networksxe2x80x9d] by J. Eldin and K. P. Lathia. As explained in the above document, in a physical private network, the various sites or nodes are connected by dedicated circuits whereas in a virtual private network each node is connected to the nearest local central office of the public network, where appropriate software sets up connections on demand. There are two variants of the virtual private network: on the one hand, semi-permanent connections can be provided and set up without dialing as soon as one of the nodes needs the circuit and which always connect the same two points. This can be the case for signaling links in particular, in an application on an integrated services digital network. On the other hand, switched connections can be provided, which can be set up only by dialing. The remainder of the description considers physical or virtual private networks made up of nodes connected by trunks which can be of any type: trunks comprising dedicated connections or trunks formed using an external network; the external network can be of any kind: the public switched network, a public land mobile network, an integrated services digital network, another private network, etc.
The problem arises in telecommunication networks of routing calls, i.e. of choosing the trunks to convey a call across the network, where appropriate with overflow to an external network. The objective of call routing is to set up a connection to convey the call in conjunction with distributing the call load across the network. In a manner that is well known in the art, routing calculations are carried out using a cost function defined for the trunks of the network. The function assigns each trunk a cost representative of the risk of blocking of the trunk; a cost function can be chosen that is calculated as the ratio between the resources required and the resources ovailable on the trunk:
cost:=required resources/available resources
In this case the best route is the one which minimizes the sum of the costs of the trunks constituting the route. A routing calculation is usually performed at the time of setting up a connection to convey the call.
It is well known in the art for calls in a private network to have different priorities. Choosing a high priority enables preferential routing of a call, if necessary by pre-empting resources of the private network which are being used by connections having a lower priority.
It has previously been proposed to manage priorities by defining a priority level and an activation mode for each call. The priority level is an integer, for example, and the activation mode is chosen from the following list:
unprotected call;
non-pre-empting protected call;
pre-empting protected call.
Using the above solution, a protected call cannot be pre-empted by another call. In other words, pre-emption applies to the lowest priority level unprotected call resources. It has also been previously proposed, in the event of network congestion, to apply the following constraints to routing a call:
the maximum priority of all the calls pre-empted to route a call must be as low as possible,
the number of calls pre-empted must be as low as possible, and
the overall routing cost must be as low as possible.
The invention addresses the problem of routing calls in a network which goes as far as possible towards satisfying the various priority constraints.
The problem of connection regression also arises in private networks. Because the networks convey different types of call (voice, data or other), different protocols propose, as a grade of service, connections having different allocated throughputs. This applies to the X25 or Frame Relay protocols, for example, which authorize fallback to smaller bandwidths if the required bandwidth is not available.
Another problem addressed by the invention is that of simultaneously managing the allocated throughputs and the priorities when routing calls. The invention manages the priorities as a function of throughput classes.
To this end, the invention proposes a method of routing a call in a network with a plurality of nodes connected by trunks wherein each call is assigned a priority level as a function of which it is able to pre-empt calls in the network, the method comprising the calculation of the cost of various routes for routing the call and choosing one route as a function of the cost, wherein the cost of a route is a vector having a first component equal to the maximum value on the trunks constituting the route of the priority level of calls pre-empted on each of the trunks, a second component equal to the number of calls pre-empted on the trunks per priority level, and a third component equal to the sum of a decreasing function of the quantity of resources available on each of the trunks, and the second component of a given cost vector is less than the second component of another cost vector if, for the highest priority level for which the second components are different, the second component of the given cost vector is less than the second component of the other cost vector.
In this case, the aforementioned choice minimizes the cost of the route for an order relationship in which a first vector is less than a second vector if the first component of the first vector is less than the first component of the second vector, or, if the first components are equal, if the second component of the first vector is less than the second component of the second vector, or, if the first and second components are equal, if the third component of the first vector is less than the third component of the second vector.
In another embodiment the network routes calls at different throughputs, with the possibility of throughput regression, and the cost of a route is also a function of the throughput that the route can carry.
To this end the invention proposes a method of routing a call in a network with a plurality of nodes connected by trunks wherein each call is assigned a priority level as a function of which it can pre-empt calls in the network, the method including calculating the cost of various routes for routing the call and choosing a route as a function of the cost, wherein the network routes calls at different throughputs, with the possibility of throughput regression, and wherein the cost of a route is also a function of the throughput that can be conveyed on the route, the cost of a route being a vector having a first component equal to the regression on the route of the throughput requested for a call, a second component equal to the maximum value of the minimum priority level of the pre-empted calls of each of the trunks constituting the route, a third component equal to the number of pre-empted calls on the trunks, and a fourth component equal to the sum of a decreasing function of the quantity of resources available on each of the trunks, and the third component of a given cost vector is less than the third component of another cost vector if, for the highest priority level for which the third components are different, the third component of the given cost vector is less than the third component of the other cost vector.
In this case, the aforementioned choice minimizes the cost of the route for an order relationship in which a first vector is less than a second vector if the first component of the first vector is less than the first component of the second vector, or, if the first components are equal, if the second component of the first vector is less than the second component of the second vector, or, if the first and second components are equal, if the third component of the first vector is less than the third component of the second vector, or, if the first, second and third components are equal, if the fourth component of the first vector is less than the fourth component of the second vector.
In one embodiment the route cost is calculated iteratively by adding the various trunks constituting the route successively.
The Dijkstra algorithm con also be used to calculate the various routes and to choose the one route.
Other features and advantages of the invention will become apparent on reading the following description of embodiments of the invention, given by way of example and with reference to the accompanying drawing.